package com.zhang.sort;

import java.util.Arrays;

/**
 * 插入排序
 *
 * @author Lelezhang
 * @create 2019-12-08 19:57
 */
public class InsertSort {
    public static void main(String[] args) {
        //冒泡排序实现,事件复杂度o(n^2),n是数组长度,两次for循环
        //创建数据
        int[] arr = {5, 1, -12, -9, 16};
        System.out.println("排序前:" + Arrays.toString(arr));
        //调用冒泡排序
        int[] result = InsertSort(arr);
        //输出结果
        System.out.println("排序后:" + Arrays.toString(result));

        //测试100W数据时间
        int[] testArr = new int[100000];
        for (int i = 0; i < 100000; i++) {
            testArr[i] = (int) (Math.random() * 1000000);
        }

        //耗时约1s
        long start = System.currentTimeMillis() / 1000;
        InsertSort(testArr);
        long end = System.currentTimeMillis() / 1000;
        System.out.println("10W数据插入排序优化后耗时:" + (end - start) + " s");
    }

    //插入排序,给出一个数组,耗时约40s
    public static int[] InsertSort(int[] arr) {
        int insertValue = 0;
        int insertIndex = 0;
        for (int i = 1; i < arr.length; i++) {
            //定义待插入的数值
            insertValue = arr[i];
            //定义待插入数值前一个数的索引
            insertIndex = i-1;
            //索引不得越界      insertIndex >= 0
            //没有找到插入位置 insertValue < arr[insertIndex]
            //待插入数小于有序表中的这个数时,有序表中的这个数后移;
            while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                //索引后后移
                insertIndex--;
            }
            //循环退出后,说明找到插入位置insertIndex+1
            //判断是否需要赋值,如果插入数本来就在插入位置就不用赋值
            if (insertIndex + 1 != i) {
                arr[insertIndex + 1] = insertValue;
            }
        }
        return arr;
    }


}
